package com.leetcode.根据数据结构分类.二叉树;

import com.leetcode.datastructure.TreeNode;

import java.util.LinkedList;

/**
 * @author: ZhouBert
 * @date: 2020/11/26
 * @description: 翻转二叉树 https://leetcode-cn.com/problems/invert-binary-tree/
 * 其实就是将所有节点的左右子树交换一遍！（这点我还没有想到这么深入）
 * -> 只要能遍历所有的节点就可以
 * -> 可以用四种遍历实现（先序遍历，中序遍历，后序遍历，层序遍历）
 */
public class A_226_翻转二叉树 {

	/**
	 * 在昨天刷了4,5 题以及听了不少劲歌以后，今天已经动不了脑子了...
	 * 于是我让身体热乎了下，提升了紧张感！终于可以继续刷题了！
	 * --
	 * 假设之后，验证流程，写伪代码，再次验证流程
	 * 站在层次遍历的基础上就是木有问题
	 * --
	 * 但是这种是通过打印式，而不是通过转换的方式
	 *
	 * @param root
	 * @return
	 */
	public static TreeNode invertTreeByLevelOrder(TreeNode root) {
		if (root == null) {
			return root;
		}
		TreeNode newRoot = new TreeNode(root.val);

		LinkedList<TreeNode> oldQueue = new LinkedList<>();
		TreeNode cur = root;

		LinkedList<TreeNode> newQueue = new LinkedList<>();
		TreeNode newCur = newRoot;

		//preset
		oldQueue.offer(cur);
		newQueue.offer(newCur);
		while (!oldQueue.isEmpty()) {
			cur = oldQueue.poll();
			newCur = newQueue.poll();
			if (cur.left != null) {
				oldQueue.offer(cur.left);
				TreeNode node = new TreeNode(cur.left.val);
				newCur.right = node;
				newQueue.offer(node);
			}
			if (cur.right != null) {
				oldQueue.offer(cur.right);
				TreeNode node = new TreeNode(cur.right.val);
				newCur.left = node;
				newQueue.offer(node);
			}
		}
		return newRoot;
	}


	/**
	 * 当接受了将所有节点转换的思路后，就使用 先序遍历，中序遍历，后序遍历进行实现
	 * 首先是先序遍历（使用递归）
	 *
	 * @param root
	 * @return
	 */
	public static TreeNode invertTreeByPreorder(TreeNode root) {
		if (root == null) {
			return null;
		}
		//先交换
		TreeNode node = root.left;
		root.left = root.right;
		root.right = node;

		invertTreeByPreorder(root.left);
		invertTreeByPreorder(root.right);
		return root;
	}

	/**
	 * 然后中序遍历
	 * 此时需要考虑交换过程在中间，避免重复交换
	 *
	 * @param root
	 * @return
	 */
	public static TreeNode invertTreeByInorder(TreeNode root) {
		if (root == null) {
			return null;
		}
		//先交换
		invertTreeByInorder(root.left);
		TreeNode node = root.left;
		root.left = root.right;
		root.right = node;
		invertTreeByInorder(root.left);
		return root;
	}

	/**
	 * 最后通过 后序遍历
	 *
	 * @param root
	 * @return
	 */
	public static TreeNode invertTreeByPostorder(TreeNode root) {
		if (root == null) {
			return null;
		}
		invertTreeByPostorder(root.left);
		invertTreeByPostorder(root.right);
		//先交换
		TreeNode node = root.left;
		root.left = root.right;
		root.right = node;
		return root;
	}

	/**
	 * 通过层次遍历进行反转
	 * 【这个看似不太好想通，目标反转左右节点，多模拟几次】
	 * @param root
	 * @return
	 */
	public static TreeNode invertTreeByLevelOrder4ExChange(TreeNode root) {
		if (root == null) {
			return null;
		}
		LinkedList<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			TreeNode cur = queue.poll();

			//在层序遍历的结构上进行转换左右子树
			TreeNode node = cur.left;
			cur.left = cur.right;
			cur.right = node;

			if (cur.left != null) {
				queue.offer(cur.left);
			}
			if (cur.right != null) {
				queue.offer(cur.right);
			}
		}
		return root;
	}


	public static void main(String[] args) {
		TreeNode root = new TreeNode(4);
		root.left = new TreeNode(2);
		root.right = new TreeNode(7);
		root.left.left = new TreeNode(1);
		root.left.right = new TreeNode(3);
		root.right.left = new TreeNode(6);


	}
}
